{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 全局路径规划算法——动态规划算法\n",
    "\n",
    "<center><img src=\"https://img-blog.csdnimg.cn/fdadf22970e9498cb421b16fa3845598.png\" width=40%>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 状态节点定义\n",
    "\n",
    "\n",
    "从后往前定义"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = {\n",
    "    '4': {'D1': {'E': 5}, 'D2': {'E': 2}},\n",
    "    '3': {'C1': {'D1': 3, 'D2': 9}, 'C2': {'D1': 6, 'D2': 5}, 'C3': {'D1': 8, 'D2': 10}},\n",
    "    '2': {'B1': {'C1': 12, 'C2': 14, 'C3': 10}, 'B2': {'C1': 6, 'C2': 10, 'C3': 4}, 'B3': {'C1': 13, 'C2': 12, 'C3': 11}},\n",
    "    '1': {'A': {'B1': 2, 'B2': 5, 'B3': 1}}\n",
    "    }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 最优路径及其距离值定义"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [],
   "source": [
    "inf = float('inf')\n",
    "dists = {\n",
    "    'A': inf,\n",
    "    'B1': inf,\n",
    "    'B2': inf,\n",
    "    'B3': inf,\n",
    "    'C1': inf,\n",
    "    'C2': inf,\n",
    "    'C3': inf,\n",
    "    'D1': inf,\n",
    "    'D2': inf,\n",
    "    'E': 0\n",
    "    }\n",
    "\n",
    "path_opt = {\n",
    "    'A': ['A'],\n",
    "    'B1': ['B1'],\n",
    "    'B2': ['B2'],\n",
    "    'B3': ['B3'],\n",
    "    'C1': ['C1'],\n",
    "    'C2': ['C2'],\n",
    "    'C3': ['C3'],\n",
    "    'D1': ['D1'],\n",
    "    'D2': ['D2'],\n",
    "    'E': ['E']\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 最优时每一个节点的父节点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 每一个节点的父节点\n",
    "parents = {\n",
    "    'A': None,\n",
    "    'B1': None,\n",
    "    'B2': None,\n",
    "    'B3': None,\n",
    "    'C1': None,\n",
    "    'C2': None,\n",
    "    'C3': None,\n",
    "    'D1': None,\n",
    "    'D2': None,\n",
    "    'E': None\n",
    "    }\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 动态规划"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {},
   "outputs": [],
   "source": [
    "def DP(graph, dists, parents):\n",
    "    for period_key in graph.keys():  # 遍历每一个阶段\n",
    "        for key_i in graph[period_key].keys():  # 遍历每个阶段的每一个状态节点\n",
    "            min_key = None\n",
    "            for key_i_dist in graph[period_key][key_i].keys(): # 遍历当前阶段的每个状态节点到下一阶段的每一条路径\n",
    "                if graph[period_key][key_i][key_i_dist] + dists[key_i_dist] < dists[key_i]:\n",
    "                    dists[key_i] = graph[period_key][key_i][key_i_dist] + dists[key_i_dist]\n",
    "                    parents[key_i] = key_i_dist\n",
    "                    min_key = key_i_dist  # 找出最小距离值的节点\n",
    "            path_opt[key_i].extend(path_opt[min_key])  # 将最小距离值的节点添加到最优路径集合\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "E到每个节点的最短距离：\n",
      " {'A': 19, 'B1': 20, 'B2': 14, 'B3': 19, 'C1': 8, 'C2': 7, 'C3': 12, 'D1': 5, 'D2': 2, 'E': 0}\n",
      "====================\n",
      "最优时每个节点的父节点：\n",
      " {'A': 'B2', 'B1': 'C1', 'B2': 'C1', 'B3': 'C2', 'C1': 'D1', 'C2': 'D2', 'C3': 'D2', 'D1': 'E', 'D2': 'E', 'E': None}\n",
      "====================\n",
      "最优路径：\n",
      " {'A': ['A', 'B2', 'C1', 'D1', 'E'], 'B1': ['B1', 'C1', 'D1', 'E'], 'B2': ['B2', 'C1', 'D1', 'E'], 'B3': ['B3', 'C2', 'D2', 'E'], 'C1': ['C1', 'D1', 'E'], 'C2': ['C2', 'D2', 'E'], 'C3': ['C3', 'D2', 'E'], 'D1': ['D1', 'E'], 'D2': ['D2', 'E'], 'E': ['E']}\n"
     ]
    }
   ],
   "source": [
    "DP(graph, dists, parents)\n",
    "print(\"E到每个节点的最短距离：\\n\",dists)\n",
    "print(\"====================\")\n",
    "print(\"最优时每个节点的父节点：\\n\",parents)\n",
    "print(\"====================\")\n",
    "print(\"最优路径：\\n\",path_opt)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "0c7484b3574347463e16b31029466871583b0d4e5c4ad861e8848f2d3746b4de"
  },
  "kernelspec": {
   "display_name": "Python 3.8.12 ('gobigger')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.12"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
